package gold.digger;

import gold.vo.TreeNode;
import javafx.util.Pair;

import java.util.*;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC872 {
    public long startExecuteTime = System.currentTimeMillis();


    /*
     * @param 此题目参考了别人代码
     * 不是因为复杂，而是因为经典
     * 经典的递归转栈
     * 未来需要再次复习此道题目
     * @return:
     */
    class Solution {
        public boolean leafSimilar(TreeNode t1, TreeNode t2) {
            List<Integer> l1 = new ArrayList<>(), l2 = new ArrayList<>();
            process(t1, l1);
            process(t2, l2);
            if (l1.size() == l2.size()) {
                for (int i = 0; i < l1.size(); i++) {
                    if (!l1.get(i).equals(l2.get(i))) return false;
                }
                return true;
            }
            return false;
        }

        void process(TreeNode root, List<Integer> list) {
            Deque<TreeNode> d = new ArrayDeque<>();
            while (root != null || !d.isEmpty()) {
                while (root != null) {
                    d.addLast(root);
                    root = root.left;
                }
                root = d.pollLast();
                if (root.left == null && root.right == null) list.add(root.val);
                root = root.right;
            }
        }
    }


    class Solution_Wrong_thought {
        public boolean leafSimilar(TreeNode root1, TreeNode root2) {
            return false;
        }

        public String getBothSide(TreeNode root) {
            if (null == root) return null;

            TreeNode cur = root, pre = null;
            String res = "";
            while (null != cur) {
                pre = cur;
                cur = null == cur.left ? cur.right : cur.left;
            }
            res += getIntStr(pre.val);
            cur = root;
            pre = null;

            while (null != cur) {
                pre = cur;
                cur = null == cur.right ? cur.left : cur.right;
            }
            res += "_" + getIntStr(pre.val);
            return res;
        }

        public String getIntStr(Integer num) {
            if (null == num) return "N";
            return String.valueOf(num);
        }
    }

    public void run() {
        Solution solution = new Solution();
        List<Integer> list = new ArrayList<>();
        System.out.println(solution.toString());
    }

    public static void main(String[] args) throws Exception {
        LC872 an = new LC872();
//        an.run();

        System.out.println(String.valueOf(null));
        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
